package stack

// 接雨量
func trap(height []int) (ans int) {
	//存储墙的下标
	stack := []int{}

	for i, h := range height {
		//比较栈顶下标
		for len(stack) > 0 && h > height[stack[len(stack)-1]] {
			//取出栈顶元素
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			left := stack[len(stack)-1]
			w := i - left - 1
			h := min(height[left], h) - height[top]
			ans += w * h
		}
		stack = append(stack, i)
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
